
#include "stdafx.h"
#include "MaxWeightStuff.h"
#include "Graph.h"

using namespace GraphTools;
using namespace MaxWeightStuff;

namespace SiloachReducer
{
	DCWMSResolver::DCWMSResolver(int vertexCount, vector<EdmondsEdge> edges, int degree)
	{
		this->Degree = degree;
		this->OriginalEdges = edges;
		this->TransformedGraph = vector<EdmondsEdge>();
		this->OriginalVertexCount = vertexCount;
		this->VertexCounter = vertexCount * 2;
		//this->riferimenti = vector<int>(vertexCount * 2);
		//for (int i = 0; i < riferimenti.size(); i++)
		//{
		//	riferimenti[i] = -1;
		//}

		for (int i = 0; i < edges.size(); i++)
		{
			int w = edges[i][2];
			int min = VertexCounter++;
			int max = VertexCounter++;
			int u = edges[i][0];
			int v = edges[i][1];
			if (u > v)
			{
				int tmp = u;
				u = v;
				v = tmp;
			}

			//riferimenti[u * 2] = u;
			//riferimenti[u * 2 + 1] = u;
			//riferimenti[v * 2] = v;
			//riferimenti[v * 2 + 1] = v;
			//riferimenti.push_back(v);
			//riferimenti.push_back(u);

			this->TransformedGraph.push_back(EdmondsEdge(u * 2, min, w));
			this->TransformedGraph.push_back(EdmondsEdge(u * 2 + 1, min, w));
			this->TransformedGraph.push_back(EdmondsEdge(v * 2, max, w));
			this->TransformedGraph.push_back(EdmondsEdge(v * 2 + 1, max, w));
			this->TransformedGraph.push_back(EdmondsEdge(min, max, w));

		}
	}
	vector<pair<int, int>> DCWMSResolver::Resolve()
	{
		vector<int> res = MaxWeightedResolver().MaxWeightedMatching(TransformedGraph);
		vector<bool> AlreadyVisited = vector<bool>(res.size());
		vector<pair<int, int>> result = vector<pair<int, int>>();
			
		for (int i = 0; i < res.size(); i++)
		{
			AlreadyVisited[i] = false;
		}


		for (int i = 0; i < this->OriginalVertexCount * 2 /*res.size()*/; i++)
		{
			if (AlreadyVisited[i])
				continue;
			if (res[i] == -1)
				continue;
			int v = min(i, res[i]);
			int endPoint = max(res[i], i);
			int otherEndPoint = endPoint % 2 == 0 ? endPoint + 1 : endPoint - 1;
			if (res[otherEndPoint] == -1)
			{
				continue;
				throw "errors";
			}
			int lastV = res[otherEndPoint];

			AlreadyVisited[i] = true;
			AlreadyVisited[res[i]] = true;
			AlreadyVisited[endPoint] = true;
			AlreadyVisited[otherEndPoint] = true;
			AlreadyVisited[lastV] = true;

			//if (riferimenti[endPoint] != riferimenti[lastV] && riferimenti[otherEndPoint] != riferimenti[v])
			//	throw "riferiments error";

			result.push_back(pair<int,int>(v / 2, lastV / 2));

		}

		return result;
	}
}